package com.liufei1988.singleLinkedList;

import java.util.Hashtable;

public class MyLinkedList {
    /**
     * 链表的头结点
     */
    private Node head=null;

    /**
     * 添加节点
     */
    private void  addNode(int data){
        Node newNode=new Node(data);
        if (head==null){
            head=newNode;
            return;
        }
        Node tmp=head;
         while (tmp.next!=null){
             System.out.println(tmp.hashCode()+"   "+head.hashCode());
             tmp=tmp.next;

         }
         tmp.next=newNode;

    }

    /**
     * 求链表长度
     */
    public int length(){
        int length=0;
        Node curNode=head;
        while (curNode.next!=null){
            length++;
            curNode=curNode.next;
        }
        return length;
    }

    /**
     * 删除链表节点
     * 把要删除节点的前节点指向要删除节点的后节点，即直接跳过待删除节点
     * @param index
     */
    public boolean deleteNode(int index){
        if (index<0 || index >length()){
            return false;
        }
        if (index==0){//删除头结点
            head=head.next;
            return true;
        }
        Node preNode=head;
        Node curNode=preNode.next;
        int i=1;
        while (curNode!=null){
            if (i==index){  //寻找待删除的节点
                preNode.next=curNode.next;  //待删除节点的前节点指向待删除节点的后节点
                return true;
            }
            //当先节点和前节点同时向后移
            preNode=preNode.next;
            curNode=curNode.next;
            i++;
        }
        return false;
    }

    /**
     * 链表节点排序。并返回排序节点的头结点
     * 选择排序法，即每次都选出来未排序节点中最小的值，与第一个未排序节点交换
     * @return
     */
    public Node linkSort(){
        Node curNode=head;
        while (curNode!=null){
            Node nextNode=curNode.next;
            while (nextNode!=null){
                if (curNode.data>nextNode.data){
                    int tmp=curNode.data;
                    curNode.data=nextNode.data;
                    nextNode.data=tmp;
                }
                nextNode=nextNode.next;
            }
            curNode=curNode.next;
        }
        return head;
    }

    /**
     * 去掉重复元素
     * 需要额外的存储空间hashtable,调用hashtable.containsKey()来判断重复节点
     */
    public void distinctLink(){
        Node tmp=head;
        Node pre=null;
        Hashtable<Integer,Integer> hb=new Hashtable<>();
        while (tmp!=null){
            if (hb.containsKey(tmp.data)){//如果表中已存在该节点，则跳过该节点
                pre.next=tmp.next;
            }else {//如果hash表中不存在该节点，将节点存到hashtable中
                hb.put(tmp.data,1);
                pre=tmp;
            }
            tmp=tmp.next;
        }
    }

    /**
     * 返回倒数第k个节点
     * 两个指针，第一个指针向前移动k-1次，之后两个指针共同移动
     * 当前面的指针到达末尾时，后面的指针所在的位置就是倒数第k个位置
     * @param k
     * @return
     */
    public Node findReverNode(int k){
        //1,2,3,4,5,6,7,8,9
        //3
        //第k个节点不存在
        if (k<1 || k>length()){
            return null;
        }
        Node first=head;
        Node second=head;
        for (int i=0;i<k-1;i++){
            first=first.next;
        }
        while (first.next!=null){
            first=first.next;
            second=second.next;
        }
        return second;
    }

    /**
     * 查找正数k个元素
     * @param k
     */
    public Node findNode(int k){
        if (k<1||k>length()){
            return null;
        }
        Node temp=head;
        for (int i=0;i<k-1;i++){
            temp=temp.next;
        }
        return temp;
    }

    /**
     * 反转链表，在反转指针线一定要保存下一节点的指针
     * @return
     */
    public void reserveLink(){
        // 1,2,3,4,5,6,7,8,9
        Node curNode=head;
        Node preNode=null;
        while (curNode!=null){
            Node nextNode=curNode.next; //保留下一节点
            curNode.next=preNode;//指针反转
            preNode=curNode;//前节点后移
            curNode=nextNode;//当前节点后移
        }
        head=preNode;

    }

    /**
     * 反向输出链表，三种方式
     * 1. 先反转链表，在输出链表，需要链表遍历两次
     * 2. 把链表中的数字放入栈中在输出，需要维护额外的栈空间
     * 3. 依据方法2中的思想，通过递归来实现，递归其实就是将先执行的数据压入栈中，再一次出栈
     * @param node
     */
    public void reservePrt(Node node){
        if (node!=null){
            reservePrt(node.next);
            System.out.println(node.data+"  ");
        }
    }

    /**
     * 寻找单链表的中间节点
     * 方法一. 求出链表的长度，在遍历1/2链表长度，寻找连表中间节点
     * 方法二：
     *  用两个指针遍历链表，一个快指针，一个慢指针
     *  快指针每次向前移动两个节点，慢指针每次向前移动一个节点
     *  当快指针移动到链表的末尾，慢指针所在的位置即为中间节点所在的位置
     * @return
     */
    public Node findModdleNode(){
        Node slowPoint=head;
        Node quickNode=head;
        //quickPoint.next==null是链表节点个数为奇数时，快指针已经走到最后了
        //quickPoint.next.next==null是链表节点数为偶数时，快指针已经走到倒数第二个节点了
        //链表节点个数为奇数时，返回的是中间节点，链表节点数为偶数时，返回的是中间节点中的前一个
        while (quickNode.next!=null&&quickNode.next.next!=null){
            slowPoint=slowPoint.next;
            quickNode=quickNode.next.next;
        }
        return slowPoint;
    }

    /**
     * 判断链表是否有环：
     * 设置快指针和慢指针，慢指针每次走一步，快指针每次走两步
     * 当快指针和慢指针相等时，说明该链表有环
     * @return
     */
    public boolean isRinged(){
        if (head==null){
            return false;
        }
        Node slow=head;
        Node quick=head;
        while (quick.next!=null&&quick.next.next!=null){
            slow=slow.next;
            quick=quick.next.next;
            if (slow==quick){
                return true;
            }
        }
        return false;
    }

    /**
     * 返回链表最后一个节点
     */
    public Node getLastNode(){
        Node temp =head;
        while (temp.next!=null){
            temp=temp.next;
        }
        return temp;
    }

    /**
     * 在不知道头结点的情况下删除指定节点
     * 删除节点的重点在于找出其前节点，使其前节点的指针指向其后节点，即跳过删除节点
     * 1. 如果待删除的是尾节点，由于单链表不知道其前节点，没有办法删除
     * 2. 如果删除的节点不是尾节点，则将该节点的值与下一个节点交换，然后该节点的指针指向下一节点的后续节点
     * @return
     */
    public boolean deleteSpecialNode(Node node){
        if (node.next==null){
            return false;
        }else {
            //交换节点和其后续节点中的数据
            int temp=node.data;
            node.data=node.next.data;
            node.next.data=temp;
            //删除后续节点
            node.next=node.next.next;
            return true;
        }

    }

    /**
     * 判断两个链表是否相交：
     *   两个链表相交，则他们的尾节点一定相同，比较两个链表的尾节点是否相同即可
     * @param head1
     * @param head2
     * @return
     */
    public boolean isCross(Node head1,Node head2){
        Node temp1=head1;
        Node temp2=head2;
        while (temp1.next!=null){
            temp1=temp1.next;
        }
        while (temp2.next!=null){
            temp2=temp2.next;
        }
        if (temp1==temp2){
            return true;
        }
        return false;
    }

    /**
     * 如果链表相交，求链表相交的起始点
     *   1. 首先判断链表是否相交，如果两表不相交，则求相交起点没有意义
     *   2. 求两个链表长度之差: len=length1-length2;
     *   3. 较长的链表先走len步
     *   4. 如果两个链表同步向前移动，没移动一次就比较他们节点是否相同，第一个相等的节点即为他们的第一个相交点
     * @param myLinkedList1
     * @param myLinkedList2
     * @return
     */
    public Node findFirstCrossPoint(MyLinkedList myLinkedList1,MyLinkedList myLinkedList2){
        //链表不相交
        if (!isCross(myLinkedList1.head,myLinkedList2.head)){
            return null;
        }else {
            int length1=myLinkedList1.length();
            int length2=myLinkedList2.length();
            Node temp1=myLinkedList1.head;//链表1的头节点
            Node temp2=myLinkedList2.head;//链表2的头节点
            int len=length1=length2;  //链表1和链表2的长度差
            if (len>0){//链表1比链表2长，链表1先移len步
                for (int i=0;i<len;i++){
                    temp1=temp1.next;
                }
            }else {//链表2比链表1长，链表2先移len步
                for (int i=0;i<len;i++){
                    temp2=temp2.next;
                }
            }
            //链表1和链表2同时迁移，直到找到链表1和链表2的相交点
            while (temp1!=temp2){
                temp1=temp1.next;
                temp2=temp2.next;
            }
            return temp1;
        }

    }

    public static void main(String[] args) {
        MyLinkedList myLinkedList=new MyLinkedList();
        myLinkedList.addNode(7);
        myLinkedList.addNode(2);
        myLinkedList.addNode(9);
        myLinkedList.addNode(3);
        myLinkedList.addNode(5);
        myLinkedList.addNode(5);
        myLinkedList.addNode(5);
        myLinkedList.addNode(5);
        myLinkedList.linkSort();
//        myLinkedList.deleteNode(1);
        myLinkedList.distinctLink();
        String a="5";
        String b=a;
        b="10";
        System.out.println(a);

    }
}
